package listbyorder.access301_400.test380;

import java.util.HashMap;
import java.util.Random;

// 双HashMap索引
public class RandomizedSet {

    int size;
    HashMap<Integer, Integer> IndexNumMap;
    HashMap<Integer, Integer> NumIndexMap;

    /**
     * Initialize your data structure here.
     */
    public RandomizedSet() {
        size = 0;
        IndexNumMap = new HashMap<>();
        NumIndexMap = new HashMap<>();
    }

    /**
     * Inserts a value to the set. Returns true if the set did not already contain the specified element.
     */
    public boolean insert(int val) {
        if (NumIndexMap.containsKey(val)) {
            return false;
        }
        IndexNumMap.put(size, val);
        NumIndexMap.put(val, size++);
        return true;
    }

    /**
     * Removes a value from the set. Returns true if the set contained the specified element.
     */
    public boolean remove(int val) {
        if (NumIndexMap.containsKey(val)) {
            --size;
            int index = NumIndexMap.get(val);
            if (index != size) {
                int tailNum = IndexNumMap.get(size);   // 获取最后加入的元素
                IndexNumMap.put(index, tailNum);
                NumIndexMap.put(tailNum, index);
            }
            IndexNumMap.remove(size);
            NumIndexMap.remove(val);
            return true;
        } else {
            return false;
        }
    }

    /**
     * Get a random element from the set.
     */
    public int getRandom() {
        if (size == 0) throw new RuntimeException("结构为空");
        Random rand = new Random();
        int random = rand.nextInt(size);
        return IndexNumMap.get(random);
    }
}
